package cn.cxq.learning.recursion;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * 骑士周游问题（又称马踏棋盘问题）回溯加贪心
 * 典型难求一解。
 * 千万不要想着求全部解！！！（我们做一个简单的假设，虽然这个预估不准确，每次马的下一步基本有8种可能，共需要下64步，既有8的64次方种可能性，共6.2771017353866807638357894232077e+57种可能性
 * 百度了一下市面上电脑基本上一秒钟可以计算30万次，一年有31536000秒，咱们除一下，结果是6.634853009667978145437795348393e+44年 如果我们可以活这么久就可能看见结果了，到时候计算机都没了。）
 * 本例只求一解。
 */
public class KnightTour {

    private int[][] checkerboard; //棋盘，int类型数组用来记录是第几步下到了这个位置
    private int size; //棋盘大小
    private boolean succeed; //标志是否找到方案

    public KnightTour(int size) {

        this.size = size;
        this.checkerboard = new int[size][size];
        for (int i = 0; i < this.checkerboard.length; i++) {
            for (int j = 0; j < this.checkerboard[0].length; j++) {
                this.checkerboard[i][j] = 0;
            }
        }
        this.succeed = false;
    }

    public void execute(int[] point, int step) {

        if (this.succeed) {
            return;
        }

        this.checkerboard[point[0]][point[1]] = ++step;

        List<int[]> plans = getPlans(point);

        //每次采取回溯次数最少的方案（贪心算法）使用和不使用的速度简直天壤之别
        plans.sort((plan1, plan2) -> {
            List<int[]> plans1 = getPlans(plan1);
            List<int[]> plans2 = getPlans(plan2);

            return plans1.size() - plans2.size();
        });

        for (int[] plan : plans) {
            if (this.checkerboard[plan[0]][plan[1]] == 0) {
                execute(plan, step);
            }
        }

        if (step < 64 && !this.succeed) {
            this.checkerboard[point[0]][point[1]] = 0;
        } else {
            this.succeed = true;
        }
    }

    public void printCheckerboard() {
        for (int i = 0; i < this.checkerboard.length; i++) {
            for (int j = 0; j < this.checkerboard[0].length; j++) {
                System.out.print(this.checkerboard[i][j] + "\t");
            }
            System.out.println();
        }
    }

    private List<int[]> getPlans(int[] point) {

        List<int[]> plans = new ArrayList<>();

        if (point[0] - 1 >= 0 && point[1] - 2 >= 0) {
            plans.add(new int[]{point[0] - 1, point[1] - 2});
        }

        if (point[0] - 2 >= 0 && point[1] - 1 >= 0) {
            plans.add(new int[]{point[0] - 2, point[1] - 1});
        }

        if (point[0] - 2 >= 0 && point[1] + 1 < this.size) {
            plans.add(new int[]{point[0] - 2, point[1] + 1});
        }

        if (point[0] - 1 >= 0 && point[1] + 2 < this.size) {
            plans.add(new int[]{point[0] - 1, point[1] + 2});
        }

        if (point[0] + 1 < this.size && point[1] + 2 < this.size) {
            plans.add(new int[]{point[0] + 1, point[1] + 2});
        }

        if (point[0] + 2 < this.size && point[1] + 1 < this.size) {
            plans.add(new int[]{point[0] + 2, point[1] + 1});
        }

        if (point[0] + 2 < this.size && point[1] - 1 >= 0) {
            plans.add(new int[]{point[0] + 2, point[1] - 1});
        }

        if (point[0] + 1 < this.size && point[1] - 2 >= 0) {
            plans.add(new int[]{point[0] + 1, point[1] - 2});
        }

        return plans;
    }
}
